home *** CD-ROM | disk | FTP | other *** search
/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / text / mac / faqs.453 < prev    next >
Text File  |  1996-02-12  |  29KB  |  827 lines
  1. Frequently Asked Questions (FAQS);faqs.453
  2.  
  3.  
  4.  
  5. What day of the week was the second visit?
  6.  
  7. From "Mathematical Diversions" by Hunter + Madachy
  8.  
  9. ==> arithmetic/clock/day.of.week.s <==
  10. The answer is 17 days and 3 hours later, which would have been a Wednesday.
  11. This is the only other time in the same month when the two would agree at all.
  12.  
  13. In 17 days the slow clock loses 17*24*7 minutes = 2856 minutes,
  14. or 47 hours and 36 minutes.  In 3 hours more it loses 21 minutes, so
  15. it has lost a total of 47 hours and 57 minutes.  Modulo 12 hours, it
  16. has *gained* 3 minutes so as to make up the 3 minutes it was slow on
  17. Sunday.  It is now (fortnight plus 3 days) exactly accurate.
  18.  
  19. ==> arithmetic/clock/thirds.p <==
  20. Do the 3 hands on a clock ever divide the face of the clock into 3
  21. equal segments, i.e. 120 degrees between each hand?
  22.  
  23. ==> arithmetic/clock/thirds.s <==
  24. First let us assume that our clock has 60 divisions.  We will show that
  25. any time the hour hand and the minute hand are 20 divisions (120 degrees)
  26. apart, the second hand cannot be an integral number of divisions from the
  27. other hands, unless it is straight up (on the minute).
  28.  
  29. Let us use h for hours, m for minutes, and s for seconds.
  30. We will use =n to mean congruent mod n, thus 12 =5 7.
  31.  
  32. We know that m =60 12h, that is, the minute hand moves 12 times as fast
  33. as the hour hand, and wraps around at 60.
  34. We also have s =60 60m. This simplifies to s/60 =1 m, which goes to
  35. s/60 = frac(m) (assuming s is in the range 0 <= s < 60), which goes to
  36. s = 60 frac(m).  Thus, if m is 5.5, s is 30.
  37.  
  38. Now let us assume the minute hand is 20 divisions ahead of the hour hand.
  39. So m =60 h + 20, thus 12h =60 h + 20, 11h =60 20, and, finally,
  40. h =60/11 20/11 (read 'h is congruent mod 60/11 to 20/11').
  41. So all values of m are k + n/11 for some integral k and integral n,
  42. 0 <= n < 11.  s is therefore 60n/11.  If s is to be an integral number of
  43. units from m and h, we must have 60n =11 n.  But 60 and 11 are relatively
  44. prime, so this holds only for n = 0.  But if n = 0, m is integral, so
  45. s is 0.
  46.  
  47. Now assume, instead, that the minute hand is 20 divisions behind the hour hand.
  48. So m =60 h - 20, 12h =60 h - 20, 11h =60 -20, h =60/11 -20/11.
  49. So m is still k + n/11.  Thus s must be 0.
  50.  
  51. But if s is 0, h must be 20 or 40.  But this translates to 4 o'clock or
  52. 8 o'clock, at both of which the minute hand is at 0, along with the second
  53. hand.
  54.  
  55. Thus the 3 hands can never be 120 degrees apart, Q.E.D.
  56.  
  57. ==> arithmetic/consecutive.product.p <==
  58. Prove that the product of three or more consecutive natural numbers cannot be a
  59. perfect square.
  60.  
  61. ==> arithmetic/consecutive.product.s <==
  62. Three consecutive numbers:
  63.   If a and b are relatively prime, and ab is a square,
  64.   then a and b are squares. (This is left as an exercise.)
  65.  
  66.   Suppose (n - 1)n(n + 1) = k^2, where n > 1.
  67.   Then n(n^2 - 1) = k^2.  But n and (n^2 - 1) are relatively prime.
  68.   Therefore n^2 - 1 is a perfect square, which is a contradiction.
  69.  
  70. Four consecutive numbers:
  71.   n(n + 1)(n + 2)(n + 3) = (n^2 + 3n + 1)^2 - 1
  72.  
  73. Five consecutive numbers:
  74.   Assume the product is a integer square, call it m.
  75.  
  76.   The prime factorization of m must have even numbers of each prime factor.
  77.  
  78.   For each prime factor, p, of m, p >= 5, p^2k must divide one of the
  79. consecutive naturals in the product.  (Otherwise, the difference between two
  80. of the naturals in the product would be a positive multiple of a prime >= 5.
  81. But in this problem, the greatest difference is 4.) So we need only consider
  82. the primes 2 and 3.
  83.  
  84.   Each of the consecutive naturals is one of:
  85.     1)    a perfect square
  86.     2)    2 times a perfect square
  87.     3)    3 times a perfect square
  88.     4)    6 times a perfect square.
  89.  
  90.   By the shoe box principle, two of the five consecutive numbers must fall into
  91. the same category.
  92.  
  93.   If there are two perfect squares, then their difference being less than five
  94. limits their values to be 1 and 4.  (0 is not a natural number, so 0 and 1
  95. and 0 and 4 cannot be the perfect squares.)  But 1*2*3*4*5=120!=x*x where x
  96. is an integer.
  97.  
  98.   If there are two numbers that are 2 times a perfect square, then their
  99. difference being less than five implies that the perfect squares (which are
  100. multiplied by 2) are less than 3 apart, and no two natural squares differ by
  101. only 1 or 2.
  102.  
  103.   A similar argument holds for two numbers which are 3 times a perfect square.
  104.  
  105.   We cannot have the case that two of the 5 consecutive numbers are multiples
  106. (much less square multiples) of 6, since their difference would be >= 6, and
  107. our span of five consecutive numbers is only 4.
  108.  
  109.   Therefore the assumption that m is a perfect square does not hold.
  110.  
  111.   QED.
  112.  
  113. In general the equation:
  114.  
  115. y^2 = x(x+1)(x+2)...(x+n),    n > 3
  116.  
  117. has only the solution corresponding to y = 0.
  118.  
  119. This is a theorem of Rigge [O. Rigge, ``Uber ein diophantisches Problem'',
  120. IX Skan. Math. Kong. Helsingfors (1938)] and Erdos [P. Erdos, ``Note on
  121. products of consecutive integers,'' J. London Math. Soc. #14 (1939),
  122. pages 194-198].
  123.  
  124. A proof can be found on page 276 of [L. Mordell, ``Diophantine
  125. Equations'', Academic Press 1969].
  126.  
  127. ==> arithmetic/consecutive.sums.p <==
  128. Find all series of consecutive positive integers whose sum is exactly 10,000.
  129.  
  130. ==> arithmetic/consecutive.sums.s <==
  131. Generalize to find X (and I) such that
  132.     (X + X+1 + X+2 + ... + X+I) = T
  133. for any integer T.
  134.  
  135. You are asking for all (X,I) s.t. (2X+I)(I+1) = 2T.  The problem is
  136. (very) slightly easier if we don't restrict X to being positive, so
  137. we'll solve this first.
  138.  
  139. Note that 2X+I and I+1 must have different parities, so the answer
  140. to the relaxed question is N = 2*(o_1+1)*(o_2+1)*...*(o_n+1), where
  141. 2T = 2^o_0*3^o_1*...*p_n^o_n (the prime factorization); this is easily
  142. seen to be the number of ways we can break 2T up into two positive
  143. factors of differing parity (with order).
  144.  
  145. In particular, 20000 = 2^5*5^4, hence there are 2*(4+1) = 10 solutions
  146. for T = 10000.  These are (2X+I,I+1):
  147.  
  148. (32*1,5^4)   (32*5,5^3)   (32*5^2,5^2)   (32*5^3,5)   (32*5^4,1)
  149. (5^4,32*1)   (5^3,32*5)   (5^2,32*5^2)   (5,32*5^3)   (1,32*5^4)
  150.  
  151. And they give rise to the solutions (X,I):
  152.  
  153. (-296,624)   (28,124)   (388,24)   (1998,4)     (10000,0)
  154. (297,31)     (-27,179)  (-387,799) (-1997,3999) (-9999,19999)
  155.  
  156. If you require that X>0 note that this is true iff 2X+I > I+1 and
  157. hence the number of solutions to this problem is N/2 (due to the
  158. symmetry of the above ordered pairs).
  159.  
  160. ==> arithmetic/digits/all.ones.p <==
  161. Prove that some multiple of any integer ending in 3 contains all 1s.
  162.  
  163. ==> arithmetic/digits/all.ones.s <==
  164. Let n be our integer; one such desired multiple is then
  165. ( 10^(phi(n))-1 )/9.  All we need is that (n,10) = 1, and
  166. if the last digit is 3 this must be the case.  A different
  167. proof using the pigeonhole principle is to consider the sequence
  168. 1, 11, 111, ..., (10^n - 1)/9.  By previous reasoning we must
  169. have at some point that either some member of our sequence = 0 (mod n)
  170. or else some value (mod n) is duplicated.  Assume the latter, with
  171. x_a and x_b, x_b>x_a,  possesing the duplicated remainders.  We then
  172. have that x_b - x-a = 0 (mod n).  Let m be the highest power of 10
  173. dividing x_b - x_a.  Now since (10,n) = 1, we can divide by 10^m and
  174. get that (x_b - x_a)/10^m = 0 (n).  But (x_b - x_a)/10^m is a number
  175. containing only the digit 1.
  176.  
  177. Q.E.D.
  178.  
  179. ==> arithmetic/digits/arabian.p <==
  180. What is the Arabian Nights factorial, the number x such that x! has 1001
  181. digits?  How about the prime x such that x! has exactly 1001 zeroes on
  182. the tail end.  (Bonus question, what is the 'rightmost' non-zero digit in x!?)
  183.  
  184. ==> arithmetic/digits/arabian.s <==
  185. The first answer is 450!.
  186.  
  187. Determining the number of zeroes at the end of x! is relatively easy once
  188. you realize that each such zero comes from a factor of 10 in the product
  189.  
  190.    1 * 2 * 3 * ... * x
  191.  
  192. Each factor of 10, in turn, comes from a factor of 5 and a factor of 2.
  193. Since there are many more factors of 2 than factors of 5, the number of 5s
  194. determines the number of zeroes at the end of the factorial.
  195.  
  196. The number of 5s in the set of numbers 1 .. x (and therefore the number
  197. of zeroes at the end of x!) is:
  198.  
  199.   z(x) = int(x/5) + int(x/25) + int(x/125) + int(x/625) + ...
  200.  
  201. This series terminates when the powers of 5 exceed x.
  202.  
  203. I know of no simple way to invert the above formula (i.e., to find x for
  204. a given z(x)), but I can approximate it by noting that, except for the "int"
  205. function,
  206.  
  207.    5*z(x) - x = z(x)
  208.  
  209. which gives:
  210.  
  211.    x = 4*z(x) (approximately).
  212.  
  213. The given problem asked, "For what prime x is z(x)=1001".  By the above forumla,
  214. this is approximately 4*1001=4004.  However, 4004! has only
  215.  
  216.   800 + 160 + 32 + 6 + 1 = 999 zeroes at the end of it.
  217.  
  218. The numbers 4005! through 4009! all have 1000 zeroes at their end and
  219. the numbers 4010! through 4014! all have 1001 zeroes at their end.
  220.  
  221. Since the problem asked for a prime x, and 4011 = 3*7*191, the only solution
  222. is x=4013.
  223.  
  224. The problem of determining the rightmost nonzero digit in x! is somewhat more
  225. difficult.  If we took the numbers 1, 2, ... , x and removed all factors of 5
  226. (and an equal number of factors of 2), the remaining numbers multiplied
  227. together modulo 10 would be the answer.  Note that since there are still many
  228. factors of 2 left, the rightmost nonzero digit must be 2, 4, 6, or 8 (x > 1).
  229.  
  230. Letting r(x) be the rightmost nonzero digit in x!, an expression for r(x) is:
  231.  
  232.   r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10, x >= 10.
  233.  
  234. where w is 4 if int(x/10) is odd and 6 if it is even.
  235.  
  236. The values of r(x) for 0 <= x <= 9 are 1, 1, 2, 6, 4, 2, 2, 4, 2, and 8.
  237.  
  238. The way to see this is true is to take the numbers 1, 2, ..., x in groups
  239. of 10.  In each group, remove 2 factors of 10.  For example, from the
  240. set 1, 2, ..., 10, choose a factor of 2 from 2 and 6 and a factor of 5 from
  241. 5 and 10.  This leaves 1, 1, 3, 4, 1, 3, 7, 8, 9, 2.  Next, separate all the
  242. factors that came from multiples of 5.  The rightmost nonzero digit of x!
  243. can now (hopefully) be seen to be:
  244.  
  245.   r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10
  246.  
  247. where w is the rightmost digit in the number formed by multiplying the numbers
  248. 1, 2, 3, ..., 10*int(x/10) after the factors of 10 and the factors left over
  249. by the multiples of 5 have been removed.  In the example with x = 10, this
  250. would be (1 * 1 * 3 * 4 * 3 * 7 * 8 * 9) mod 10 = 4.  The "r(x mod 10)" term
  251. takes care of the numbers from 10*int(x/10)+1 up to x.
  252.  
  253. The "w" term can be seen to be 4 or 6 depending on whether int(x/10) is odd or
  254. even since, after removing 10*n+5 and 10*n+10 and a factor of 2 each from
  255. 10*n+2 and 10*n+6 from the group of numbers 10*n+1 through 10*n+10, the
  256. remaining factors (mod 10) always equals 4 and 4^t mod 10 = 4 if t is odd and
  257. 6 when t is even (t != 0).
  258.  
  259. So, finally, the rightmost nonzero digit in 4013! is found as follows:
  260.  
  261.   r(4013) = (r(802) * 4 * 6) mod 10
  262.   r(802)  = (r(160) * 6 * 2) mod 10
  263.   r(160)  = (r(32)  * 6 * 1) mod 10
  264.   r(32)   = (r(6)   * 4 * 2) mod 10
  265.  
  266. Using a table of r(x) for 0 <= x <= 9, r(6) = 2.  Then,
  267.  
  268.   r(32)   = (2 * 4 * 2) mod 10 = 6
  269.   r(160)  = (6 * 6 * 1) mod 10 = 6
  270.   r(802)  = (6 * 6 * 2) mod 10 = 2
  271.   r(4013) = (2 * 4 * 6) mod 10 = 8
  272.  
  273. Thus, the rightmost nonzero digit in 4013! is 8.
  274.  
  275. ==> arithmetic/digits/circular.p <==
  276. What 6 digit number, with 6 different digits, when multiplied by all integers
  277. up to 6, circulates its digits through all 6 possible positions, as follows:
  278. ABCDEF * 1 = ABCDEF
  279. ABCDEF * 3 = BCDEFA
  280. ABCDEF * 2 = CDEFAB
  281. ABCDEF * 6 = DEFABC
  282. ABCDEF * 4 = EFABCD
  283. ABCDEF * 5 = FABCDE
  284.  
  285. ==> arithmetic/digits/circular.s <==
  286. ABCDEF=142857 (the digits of the expansion of 1/7).
  287.  
  288. ==> arithmetic/digits/divisible.p <==
  289. Find the least number using 0-9 exactly once that is evenly divisible by each
  290. of these digits?
  291.  
  292. ==> arithmetic/digits/divisible.s <==
  293. Since the sum of the digits is 45, any permutation of the digits gives a
  294. multiple of 9.  To get a multiple of both 2 and 5, the last digit must
  295. be 0, and thus to get a multiple of 8 (and 4), the tens digit must be
  296. even, and the hundreds digit must be odd if the tens digit is 2 or 6,
  297. and even otherwise.  The number will also be divisible by 6, since it is
  298. divisible by 2 and 3, so 7 is all we need to check.  First, we will look
  299. for a number whose first five digits are 12345; now, 1234500000 has a
  300. remainder of 6 when divided by 7, so we have to arrange the remaining
  301. digits to get a remainder of 1.  The possible arrangements, in
  302. increasing order, are
  303.  
  304. 78960, remainder 0
  305. 79680, remainder 6
  306. 87960, remainder 5
  307. 89760, remainder 6
  308. 97680, remainder 2
  309. 98760, remainder 4
  310.  
  311. That didn't work, so try numbers starting with 12346; this is impossible
  312. because the tens digit must be 8, and the hundreds digit cannot be even.
  313. Now try 12347, and 1234700000 has remainder 2.  The last five digits can
  314. be
  315.  
  316. 58960, remainder 6
  317. 59680, remainder 5, so this works, and the number is
  318.  
  319. 1234759680.
  320.  
  321. ==> arithmetic/digits/equations/123456789.p <==
  322. In how many ways can "." be replaced with "+", "-", or "" (concatenate) in
  323. .1.2.3.4.5.6.7.8.9=1 to form a correct equation?
  324.  
  325. ==> arithmetic/digits/equations/123456789.s <==
  326.  1-2 3+4 5+6 7-8 9 = 1
  327. +1-2 3+4 5+6 7-8 9 = 1
  328.  1+2 3+4-5+6 7-8 9 = 1
  329. +1+2 3+4-5+6 7-8 9 = 1
  330. -1+2 3-4+5+6 7-8 9 = 1
  331.  1+2 3-4 5-6 7+8 9 = 1
  332. +1+2 3-4 5-6 7+8 9 = 1
  333.  1-2 3-4+5-6 7+8 9 = 1
  334. +1-2 3-4+5-6 7+8 9 = 1
  335.  1-2-3-4 5+6 7-8-9 = 1
  336. +1-2-3-4 5+6 7-8-9 = 1
  337.  1+2-3 4+5 6-7-8-9 = 1
  338. +1+2-3 4+5 6-7-8-9 = 1
  339. -1+2 3+4+5-6-7-8-9 = 1
  340. -1 2+3 4-5-6+7-8-9 = 1
  341.  1+2+3+4-5+6+7-8-9 = 1
  342. +1+2+3+4-5+6+7-8-9 = 1
  343. -1+2+3-4+5+6+7-8-9 = 1
  344.  1-2-3+4+5+6+7-8-9 = 1
  345. +1-2-3+4+5+6+7-8-9 = 1
  346.  1+2 3+4 5-6 7+8-9 = 1
  347. +1+2 3+4 5-6 7+8-9 = 1
  348.  1+2 3-4-5-6-7+8-9 = 1
  349. +1+2 3-4-5-6-7+8-9 = 1
  350.  1+2+3+4+5-6-7+8-9 = 1
  351. +1+2+3+4+5-6-7+8-9 = 1
  352. -1+2+3+4-5+6-7+8-9 = 1
  353.  1-2+3-4+5+6-7+8-9 = 1
  354. +1-2+3-4+5+6-7+8-9 = 1
  355. -1-2-3+4+5+6-7+8-9 = 1
  356.  1-2+3+4-5-6+7+8-9 = 1
  357. +1-2+3+4-5-6+7+8-9 = 1
  358.  1+2-3-4+5-6+7+8-9 = 1
  359. +1+2-3-4+5-6+7+8-9 = 1
  360. -1-2+3-4+5-6+7+8-9 = 1
  361. -1+2-3-4-5+6+7+8-9 = 1
  362. -1+2 3+4 5-6 7-8+9 = 1
  363.  1-2 3-4 5+6 7-8+9 = 1
  364. +1-2 3-4 5+6 7-8+9 = 1
  365. -1+2 3-4-5-6-7-8+9 = 1
  366. -1+2+3+4+5-6-7-8+9 = 1
  367.  1-2+3+4-5+6-7-8+9 = 1
  368. +1-2+3+4-5+6-7-8+9 = 1
  369.  1+2-3-4+5+6-7-8+9 = 1
  370. +1+2-3-4+5+6-7-8+9 = 1
  371. -1-2+3-4+5+6-7-8+9 = 1
  372.  1+2-3+4-5-6+7-8+9 = 1
  373. +1+2-3+4-5-6+7-8+9 = 1
  374. -1-2+3+4-5-6+7-8+9 = 1
  375. -1+2-3-4+5-6+7-8+9 = 1
  376.  1-2-3-4-5+6+7-8+9 = 1
  377. +1-2-3-4-5+6+7-8+9 = 1
  378.  1-2 3+4+5+6+7-8+9 = 1
  379. +1-2 3+4+5+6+7-8+9 = 1
  380.  1+2+3+4 5-6 7+8+9 = 1
  381. +1+2+3+4 5-6 7+8+9 = 1
  382.  1 2+3 4+5-6 7+8+9 = 1
  383. +1 2+3 4+5-6 7+8+9 = 1
  384.  1+2+3-4-5-6-7+8+9 = 1
  385. +1+2+3-4-5-6-7+8+9 = 1
  386. -1+2-3+4-5-6-7+8+9 = 1
  387.  1-2-3-4+5-6-7+8+9 = 1
  388. +1-2-3-4+5-6-7+8+9 = 1
  389. -1-2-3-4-5+6-7+8+9 = 1
  390. -1-2 3+4+5+6-7+8+9 = 1
  391.  1-2+3 4-5 6+7+8+9 = 1
  392. +1-2+3 4-5 6+7+8+9 = 1
  393.  1 2-3 4+5-6+7+8+9 = 1
  394. +1 2-3 4+5-6+7+8+9 = 1
  395. Total solutions  = 69
  396.  
  397. 69/19683 = 0.35 %
  398.  
  399. for those who care (it's not very elegant but it did the trick):
  400.  
  401. #include <stdio.h>
  402. #include <math.h>
  403.  
  404. main (argc,argv)
  405.      int argc;
  406.      char *argv[];
  407. {
  408.   int sresult, result, operator[10],thisop;
  409.   char buf[256],ops[3];
  410.   int i,j,tot=0,temp;
  411.  
  412.   ops[0] = ' ';
  413.   ops[1] = '-';
  414.   ops[2] = '+';
  415.  
  416.   for (i=1; i<10; i++) operator[i] = 0;
  417.  
  418.   for (j=0; j < 19683; j++) {
  419.     result = 0;
  420.     sresult = 0;
  421.     thisop = 1;
  422.     for (i=1; i<10; i++) {
  423.       switch (operator[i]) {
  424.       case 0:
  425.     sresult = sresult * 10 + i;
  426.     break;
  427.       case 1:
  428.     result = result + sresult * thisop;
  429.     sresult = i;
  430.     thisop = -1;
  431.     break;
  432.       case 2:
  433.     result = result + sresult * thisop;
  434.     sresult = i;
  435.     thisop = 1;
  436.     break;
  437.       }
  438.     }
  439.  
  440.     result  = result + sresult * thisop;
  441.     if (result == 1) {
  442.       tot++;
  443.       for  (i=1;i<10;i++)
  444.     printf("%c%d",ops[operator[i]],i);
  445.       printf(" = %d\n",result);
  446.     }
  447.     temp = 0;
  448.     operator[1] += 1;
  449.     for (i=1;i<10;i++) {
  450.       operator[i] += temp;
  451.       if (operator[i] > 2) { operator[i] = 0; temp = 1;}
  452.       else temp = 0;
  453.     }
  454.  
  455.   }
  456.  
  457.   printf("Total solutions  = %d\n" , tot);
  458. }
  459.  
  460. cwren@media.mit.edu (Christopher Wren)
  461.  
  462. ==> arithmetic/digits/equations/1992.p <==
  463. 1 = -1+9-9+2.  Extend this list to 2 - 100 on the left side of the equals sign.
  464.  
  465. ==> arithmetic/digits/equations/1992.s <==
  466. 1 = -1+9-9+2
  467. 2 = 1*9-9+2
  468. 3 = 1+9-9+2
  469. 4 = 1+9/9+2
  470. 5 = 1+9-sqrt(9)-2
  471. 6 = 1^9+sqrt(9)+2
  472. 7 = -1+sqrt(9)+sqrt(9)+2
  473. 8 = 19-9-2
  474. 9 = (1/9)*9^2
  475. 10= 1+(9+9)/2
  476. 11= 1+9+sqrt(9)-2
  477. 12= 19-9+2
  478. 13= (1+sqrt(9))!-9-2
  479. 14= 1+9+sqrt(9)!-2
  480. 15= -1+9+9-2
  481. 16= -1+9+sqrt(9)!+2
  482. 17= 1+9+9-2
  483. 18= 1+9+sqrt(9)!+2
  484. 19= -1+9+9+2
  485. 20= (19-9)*2
  486. 21= 1+9+9+2
  487. 22= (-1+sqrt(9))*(9-2)
  488. 23= (1+sqrt(9))!-sqrt(9)+2
  489. 24= -1+9*sqrt(9)-2
  490. 25= 1*9*sqrt(9)-2
  491. 26= 19+9-2
  492. 27= 1*9+9*2
  493. 28= 1+9+9*2
  494. 29= 1*9*sqrt(9)+2
  495. 30= 19+9+2
  496. 31= (1+sqrt(9))!+9-2
  497. 32= -1+sqrt(9)*(9+2)
  498. 33= 1*sqrt(9)*(9+2)
  499. 34= (-1+9+9)*2
  500. 35= -1+(9+9)*2
  501. 36= 1^9*sqrt(9)!^2
  502. 37= 19+9*2
  503. 38= 1*sqrt(9)!*sqrt(9)!+2
  504. 39= 1+sqrt(9)!*sqrt(9)!+2
  505. 40= (1+sqrt(9)!)*sqrt(9)!-2
  506. 41= -1+sqrt(9)!*(9-2)
  507. 42= (1+sqrt(9))!+9*2
  508. 43= 1+sqrt(9)!*(9-2)
  509. 44= -1+9*(sqrt(9)+2)
  510. 45= 1*9*(sqrt(9)+2)
  511. 46= 1+9*(sqrt(9)+2)
  512. 47= (-1+sqrt(9)!)*9+2
  513. 48= 1*sqrt(9)!*(sqrt(9)!+2)
  514. 49= (1+sqrt(9)!)*(9-2)
  515. 50= (-1+9)*sqrt(9)!+2
  516. 51= -1+9*sqrt(9)!-2
  517. 52= 1*9*sqrt(9)!-2
  518. 53= -1+9*sqrt(9)*2
  519. 54= 1*9*sqrt(9)*2
  520. 55= 1+9*sqrt(9)*2
  521. 56= 1*9*sqrt(9)!+2
  522. 57= 1+9*sqrt(9)!+2
  523. 58= (1+9)*sqrt(9)!-2
  524. 59= 19*sqrt(9)+2
  525. 60= (1+9)*sqrt(9)*2
  526. 61= (1+sqrt(9)!)*9-2
  527. 62= -1+9*(9-2)
  528. 63= 1*9*(9-2)
  529. 64= 1+9*(9-2)
  530. 65= (1+sqrt(9)!)*9+2
  531. 66= 1*sqrt(9)!*(9+2)
  532. 67= 1+sqrt(9)!*(9+2)
  533. 68= -(1+sqrt(9))!+92
  534. 69= (1+sqrt(9))!+(9/.2)
  535. 70= (1+9)*(9-2)
  536. 71= -1-9+9^2
  537. 72= (1+sqrt(9))*9*2
  538. 73= -19+92
  539. 74= (-1+9)*9+2
  540. 75= -1*sqrt(9)!+9^2
  541. 76= 1-sqrt(9)!+9^2
  542. 77= (1+sqrt(9)!)*(9+2)
  543. 78= -1+9*9-2
  544. 79= 1*9*9-2
  545. 80= 1+9*9-2
  546. 81= 1*9*sqrt(9)^2
  547. 82= -1+9*9+2
  548. 83= 1*9*9+2
  549. 84= 1+9*9+2
  550. 85= -1-sqrt(9)!+92
  551. 86= -1*sqrt(9)!+92
  552. 87= 1-sqrt(9)!+92
  553. 88= (1+9)*9-2
  554. 89= -1*sqrt(9)+92
  555. 90= 1-sqrt(9)+92
  556. 91= -1^9+92
  557. 92= (1+9)*9+2
  558. 93= 1^9+92
  559. 94= -1+sqrt(9)+92
  560. 95= 19*(sqrt(9)+2)
  561. 96= -1+99-2
  562. 97= 1*99-2
  563. 98= 1+99-2
  564. 99= 1*9*(9+2)
  565. 100= -1+99+2
  566.  
  567. ==> arithmetic/digits/equations/383.p <==
  568. Make 383 out of 1,2,25,50,75,100 using +,-,*,/.
  569.  
  570. ==> arithmetic/digits/equations/383.s <==
  571. You can get 383 with ((2+50)/25+1)*100+75.
  572.  
  573. Of course, if you expect / as in C, the above expression is just 375.
  574. But then you can get 383 with (25*50-100)/(1+2).  Pity there's no way
  575. to use the 75.
  576.  
  577. If we had a language that rounded instead of truncating, we could use
  578. ((1+75+100)*50)/(25-2) or (2*75*(25+100))/(50-1).
  579.  
  580. I imagine your problem lies in not dividing things that aren't
  581. divisible.
  582.  
  583. Dan Hoey
  584. Hoey@AIC.NRL.Navy.Mil
  585.  
  586. ==> arithmetic/digits/extreme.products.p <==
  587. What are the extremal products of three three-digit numbers using digits 1-9?
  588.  
  589. ==> arithmetic/digits/extreme.products.s <==
  590. There is a simple procedure which applies to these types of problems (and
  591. which can be proven with help from the arithmetic-geometric inequality).
  592.  
  593. For the first part we use the "first large then equal" procedure.
  594. This means that are three numbers will be 7**, 8**, and 9**.  Now
  595. the digits 4,5,6 get distributed so as to make our three number as
  596. close to each other as possible, i.e. 76*, 85*, 94*.  The same goes
  597. for the remaining three digits, and we get 763, 852, 941.
  598.  
  599. For the second part we use the "first small then different" procedure.
  600. Our three numbers will be of the form 1**, 2**, 3**.  We now place
  601. the three digits so as to make our three numbers as unequal as possible;
  602. this gives 14*, 25*, 36*.  Finishing, we get 147, 258, 369.
  603.  
  604. Now, *prove* that these procedures work for generalizations of this
  605. problem.
  606.  
  607. ==> arithmetic/digits/googol.p <==
  608. What digits does googol! start with?
  609.  
  610. ==> arithmetic/digits/googol.s <==
  611. I'm not sure how to calculate the first googol of digits of log10(e), but
  612. here's the first 150(approximately) of them...
  613.  
  614. 0.43429448190325182765112891891660508229439700580366656611445378316586464920
  615. 8870774729224949338431748318706106744766303733641679287158963906569221064663
  616.  
  617. We need to deal with the digits immediately after the decimal point in
  618. googol*log10(e), which are  .187061
  619.  
  620. frac[log(googol!)] = frac[halflog2pi + 50 + googol(100-log10(e))]
  621.  = frac{halflog2pi + frac[googol(100-log10(e))]}
  622.  = frac[.399090 + (1- .187061)]
  623.  = .212029
  624.  
  625. 10 ** .212029 = 1.629405
  626.  
  627. Which means that googol! starts with 1629
  628.  
  629. ==> arithmetic/digits/labels.p <==
  630. You have an arbitrary number of model kits (which you assemble for
  631. fun and profit).  Each kit comes with twenty (20) stickers, two of which
  632. are labeled "0", two are labeled "1", ..., two are labeled "9".
  633. You decide to stick a serial number on each model you assemble starting
  634. with one.  What is the first number you cannot stick.  You may stockpile
  635. unused numbers on already assembled models, but you may not crack open
  636. a new model to get at its stickers.  You complete assembling the current
  637. model before starting the next.
  638.  
  639. ==> arithmetic/digits/labels.s <==
  640. The method I used for this problem involved first coming up with a
  641. formula that says how many times a digit has been used in all n models.
  642.  
  643. n = k*10^i + m for some k,m with 0 <k <10, m < 10^i
  644. f(d,n) = (number of d's used getting to k*10^i from digits 0 to (i-1)) +
  645.     (number of d's used by #'s 10^i to n from digit i) + f(d,m)
  646. f(d,n) = i*k*10^(i-1) + (if (d < k) 10^i else if (d == k) m+1 else 0) + f(d,m)
  647.  
  648. This doesn't count 0's, which should be ok as they are not used as often
  649. as other digits.  From the formula, it is clear that f(1,n) is never
  650. less than f(d,n) for 1<d<10.
  651. So I just calculated f(1,n) for various n (with some help from bc).
  652.  
  653. I quickly discovered that for n = 2*10^15, f(1,n) = 2*n.  After further
  654. trials I determined that for n = 1999919999999981, f(1,n) = 2*n + 1.
  655. This appears to be the smallest n with f(1,n) > 2*n.
  656.  
  657. ==> arithmetic/digits/nine.digits.p <==
  658. Form a number using 0-9 once with its first n digits divisible by n.
  659.  
  660. ==> arithmetic/digits/nine.digits.s <==
  661. First, reduce the sample set. For each digit of ABCDEFGHI, such that the last
  662. digit, (current digit), is the same as a multiple of N :
  663.  
  664. A: Any number 1-9
  665. B: Even numbers 2,4,6,8 (divisible by 2).
  666. C: Any number 1-9 (21,12,3,24,15,6,27,18,9).
  667. D: Even numbers 2,4,6,8 (divisible by 4, every other even).
  668. E: 5 (divisible by 5 and 0 not allowed).
  669. F: Even numbers (12,24,6,18)
  670. G: Any number 1-9 (21,42,63,14,35,56,7,28,49).
  671. H: Even numbers (32,24,16,8)
  672. I: Any number 1-9 (81,72,63,54,45,36,27,18,9)
  673.  
  674. Since E must be 5, I can eliminate it everywhere else.
  675. Since I will use up all the even digits, (2,4,6,8) filling in those spots
  676.    that must be even. Any number becomes all odds, except 5.
  677.  
  678. A: 1,3,7,9
  679. B: 2,4,6,8
  680. C: 1,3,7,9
  681. D: 2,4,6,8
  682. E: 5
  683. F: 2,4,6,8
  684. G: 1,3,7,9
  685. H: 2,4,6,8
  686. I: 1,3,7,9
  687.  
  688. We have that 2C+D=0 (mod 4), and since C is odd,
  689. this implies that D is 2 or 6; similarly we find that H is 2 or 6 ==>
  690. {B,F} = {4,8}.  D+5+F=0 (mod 3) ==> if D=2 then F=8, if D=6 then F=4.
  691.  
  692. We have two cases.
  693.  
  694. Assume our number is of the form A4C258G6I0.  Now the case n=8 ==>
  695. G=1,9; case n=3 ==> A+1+C=0 (mod 3) ==> {A,C}={1,7} ==> G=9, I=3.
  696. The two numbers remaining fail for n=7.
  697.  
  698. Assume our number is of the form A8C654G2I0.  The case n=8 ==> G=3,7.
  699. If G=3, we need to check to see which of 1896543, 9816543, 7896543,
  700. and 9876543 are divisible by 7; none are.
  701.  
  702. If G=7, we need to check to see which of 1896547, 9816547, 1836547,
  703. and 3816547 are divisible by 7; only the last one is, which yields
  704. the solution 3816547290.
  705.  
  706. ==> arithmetic/digits/palindrome.p <==
  707. Does the series formed by adding a number to its reversal always end in
  708. a palindrome?
  709.  
  710. ==> arithmetic/digits/palindrome.s <==
  711. This is not known.
  712.  
  713. If you start with 196, after 9480000 iterations you get a 3924257-digit
  714. non-palindromic number.  However, there is no known proof that you will
  715. never get a palindrome.
  716.  
  717. The statement is provably false for binary numbers. Roland Sprague has
  718. shown that 10110 starts a series that never goes palindromic.
  719.  
  720. ==> arithmetic/digits/palintiples.p <==
  721. Find all numbers that are multiples of their reversals.
  722.  
  723. ==> arithmetic/digits/palintiples.s <==
  724. We are asked to find numbers that are integer multiples of their
  725. reversals, which I call palintiples.  Of course, all the palindromic
  726. numbers are a trivial example, but if we disregard the unit multiples,
  727. the field is narrowed considerably.
  728.  
  729. Rouse Ball (_Mathematical_recreations_and_essays_) originated the
  730. problem, and G. H. Hardy (_A_mathematician's_apology_) used the result
  731. that 9801 and 8712 are the only four-digit palintiples as an example
  732. of a theorem that is not ``serious''.  Martin Beech (_The_mathema-
  733. tical_gazette_, Vol 74, #467, pp 50-51, March '90) observed that
  734. 989*01 and 879*12 are palintiples, an observation he ``confirmed'' on
  735. a hand calculator, and conjectured that these are all that exist.
  736.  
  737. I confirm that Beech's numbers are palintiples, I will show that they
  738. are not all of the palintiples.  I will show that the palintiples do
  739. not form a regular language.  And then I will prove that I have found
  740. all the palintiples, by describing the them with a generalized form
  741. of regular expression.  The results become more interesting in other
  742. bases.
  743.  
  744. First, I have a more reasonable method of confirming that these
  745. numbers are palintiples:
  746.  
  747.     Proof:  First, letting "9*" and "0*" refer an arbitrary string of
  748.     nines and a string of zeroes of the same length, I note that
  749.  
  750.         879*12 = 879*00 + 12 = (880*00 - 100) + 12 = 880*00 - 88
  751.         219*78 = 219*00 + 78 = (220*00 - 100) + 78 = 220*00 - 22
  752.  
  753.         989*01 = 989*00 +  1 = (990*00 - 100) +  1 = 990*00 - 99
  754.         109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11
  755.  
  756.     It is obvious that 4x(220*00 - 22) = 880*00 - 88 and that
  757.     9x(110*00 - 11) = 990*00 - 99.  QED.
  758.  
  759. Now, to show that these palintiples are not all that exist, let us
  760. take the (infinite) language L[4] = (879*12 + 0*), and let Pal(L[4])
  761. refer to the set of palindromes over the alphabet L[4].  It is
  762. immediate that the numbers in Pal(L[4]) are palintiples.  For
  763. instance,
  764.  
  765.           8712 000 87912 879999912 879999912 87912 000 8712
  766.     = 4 x 2178 000 21978 219999978 219999978 21978 000 2178
  767.  
  768. (where I have inserted spaces to enhance readability) is a palintiple.
  769. Similarly, taking L[9] = (989*01 + 0*), the numbers in Pal(L[9]) are
  770. palintiples.  We exclude numbers starting with zeroes.
  771.  
  772. The reason these do not form a regular language is that the
  773. sub-palintiples on the left end of the number must be the same (in
  774. reverse order) as the sub-palintiples on the right end of the number:
  775.  
  776.          8712 8712 87999912 = 4 x 2178 2178 21999978
  777.  
  778. is not a palintiple, because 8712 8712 87999912 is not the reverse of
  779. 2178 2178 21999978.  The pumping lemma can be used to prove that
  780. Pal(L[4])+Pal(L[9]) is not a regular language, just as in the familiar
  781. proof that the palindromes over a non-singleton alphabet do not form a
  782. regular language.
  783.  
  784. Now to characterize all the palintiples, let N be a palintiple,
  785. N=CxR(N), where R(.) signifies reversal, and C>1 is an integer.  (I
  786. use "x" for multiplication, to avoid confusion with the Kleene star
  787. "*", which signifies the concatenated closure.)  If D is a digit of N,
  788. let D' refer to the corresponding digit of R(N).  Since N=CxR(N),
  789. D+10T = CxD'+S, where S is the carry in to the position occupied by D'
  790. when R(N) is multiplied by C, and T is the carry out of that position.
  791. Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the
  792. position occupied by D when R(N) is multiplied by C.
  793.  
  794. Since D and D' are so closely related, I will use the symbol D:D' to
  795. refer to a digit D on the left side of a string with a corresponding
  796. digit D' on the right side of the string.  More formally, an
  797. expression "x[1]:y[1] x[2]:y[2] ... x[n]:y[n] w" will refer to a
  798. string "x[1] x[2] ... x[n] w y[n] ... y[2] y[1]", where the x[i] and
  799. y[i] are digits and w is a string of zero or one digits.  So 989901
  800. may be written as 9:1 8:0 9:9 and 87912 may be written as 8:2 7:1 9.
  801. Thus Pal(L[4])+Pal(L[9]) (omitting numbers with leading zeroes) can be
  802. represented as
  803.  
  804.             (8:2 7:1 9:9* 1:7 2:8 0:0*)*
  805.               (0:0* + 0 + 8:2 7:1 ( 9:9* + 9:9* 9))
  806.           + (9:1 8:0 9:9* 0:8 1:9 0:0*)*
  807.               (0:0* + 0 + 9:1 8:0 ( 9:9* + 9:9* 9)).      (1)
  808.  
  809. For each pair of digits D:D', there are a very limited--and often
  810. empty--set of quadruples S,T,S',T' of digits that satisfy the
  811. equations
  812.  
  813.                     D +10T =CxD'+S
  814.                     D'+10T'=CxD +S',                      (2)
  815.  
  816. yet such a quadruple must exist for "D:D'" to appear in a palintiple
  817. with multiplier C.  Furthermore, the S and T' of one D:D' must be T
  818. and S', respectively, of the next pair of digits that appear.  This
  819. enables us to construct a finite state machine to recognize those
  820. palintiples.  The states [X#Y] refer to a pair of carries in D and D',
  821. and we allow a transition from state [T#S'] to state [S#T'] on input
  822. symbol D:D' exactly when equations (2) are satisfied.  Special
  823. transitions for a single-digit input symbol (the central digit of
  824. odd-length palintiples) and the criteria for the initial and the
  825. accepting states are left as exercises.  The finite state machines
  826. thus formed are
  827.